package algorithm.recursionAndbacktrack.p93;

import java.util.ArrayDeque;
import java.util.Iterator;

/**
 * 93. 复原 IP 地址
 */
public class Solution2 {
    public String restoreIpAddress(String s) {
        ArrayDeque<Integer> nums = new ArrayDeque<>();
        restoreIpAddress(s, nums);
        Iterator<Integer> iterator = nums.iterator();
        StringBuilder sb = new StringBuilder("" + iterator.next());
        while (iterator.hasNext()) {
            sb.append("." + iterator.next());
        }
        return sb.toString();
    }


    private boolean restoreIpAddress(String str, ArrayDeque<Integer> nums) {
        // 满了4个数字，就返回
        if (nums.size() == 4) {
            if (str.length() == 0) { // 字符没有剩余，表示一个合法的ip
                return true;
            }
            return false;
        }

        for (int i = 1; i <= 3; i++) {
            Integer num = Integer.parseInt(str.substring(0, i));
            if (num < 256) {
                nums.addLast(num);
                if (restoreIpAddress(str.substring(i), nums)) {
                    return true;
                }
                nums.removeLast();
            }
        }

        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution2().restoreIpAddress("25525511135"));
//        System.out.println(new Solution2().restoreIpAddresses("0000"));
    }
}